package com.sheng.leetcode.year2023.month05.day16;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/05/16
 * <p>
 * 1335. 工作计划的最低难度<p>
 * <p>
 * 你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。<p>
 * 你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。<p>
 * 给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。<p>
 * 返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：jobDifficulty = [6,5,4,3,2,1], d = 2<p>
 * 输出：7<p>
 * 解释：第一天，您可以完成前 5 项工作，总难度 = 6.<p>
 * 第二天，您可以完成最后一项工作，总难度 = 1.<p>
 * 计划表的难度 = 6 + 1 = 7<p>
 * <p>
 * 示例 2：<p>
 * 输入：jobDifficulty = [9,9,9], d = 4<p>
 * 输出：-1<p>
 * 解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。<p>
 * <p>
 * 示例 3：<p>
 * 输入：jobDifficulty = [1,1,1], d = 3<p>
 * 输出：3<p>
 * 解释：工作计划为每天一项工作，总难度为 3 。<p>
 * <p>
 * 示例 4：<p>
 * 输入：jobDifficulty = [7,1,7,1,7,1], d = 3<p>
 * 输出：15<p>
 * <p>
 * 示例 5：<p>
 * 输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6<p>
 * 输出：843<p>
 * <p>
 * 提示：<p>
 * 1 <= jobDifficulty.length <= 300<p>
 * 0 <= jobDifficulty[i] <= 1000<p>
 * 1 <= d <= 10<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule">1335. 工作计划的最低难度</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1335 {

    @Test
    public void test01() {
        int[] jobDifficulty = {6, 5, 4, 3, 2, 1};
        int d = 2;
//        int[] jobDifficulty = {9, 9, 9};
//        int d = 4;
//        int[] jobDifficulty = {1, 1, 1};
//        int d = 3;
//        int[] jobDifficulty = {7, 1, 7, 1, 7, 1};
//        int d = 3;
//        int[] jobDifficulty = {11, 111, 22, 222, 33, 333, 44, 444};
//        int d = 6;
        System.out.println(new Solution().minDifficulty(jobDifficulty, d));
    }
}

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        if (n < d) {
            return -1;
        } else if (n == d) {
            return Arrays.stream(jobDifficulty).sum();
        }
        // 把数组 jobDifficulty 分为 d 个子数组，求每个子数组最大值之和的最小值是多少
        int inf = 1 << 30;
        // f[i][j] 表示完成前 i 项工作，且一共用了 j 天的最小难度，初始时f[0][0] = 0，其余 f[i][j]均为无穷大
        int[][] f = new int[n + 1][d + 1];
        for (int[] ints : f) {
            Arrays.fill(ints, inf);
        }
        f[0][0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= Math.min(d, i); j++) {
                int mx = 0;
                for (int k = i; k > 0; k--) {
                    mx = Math.max(mx, jobDifficulty[k - 1]);
                    f[i][j] = Math.min(f[i][j], f[k - 1][j - 1] + mx);
                }
            }
        }
        return f[n][d] >= inf ? -1 : f[n][d];
    }
}
